﻿#-*- coding: utf-8 -*-
"""
Solveur de grilles de sudoku (backtracking).
Par Guillaume HUYSMANS, 2013.
Version non objet et non maintenue (gardée "in memoriam").
"""
import time

def ticks():
	"""
	Retourne un nombre de ticks en millisecondes.
	Utile pour chronométrer une fonction sans timeit.
	"""
	return int(round(time.time() * 1000))

def get_grid():
	"""
	Donne une grille de sudoku.
	TODO : lecture depuis un fichier.
	"""
	return [ #drôles de motifs :)
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0],
		[0, 0, 0, 0, 0, 0, 0, 0, 0]
	]
	return [ #exemple pris sur le Net
		[9, 0, 0, 0, 0, 0, 0, 1, 0],
		[0, 0, 7, 9, 1, 0, 6, 5, 0],
		[0, 8, 0, 6, 4, 0, 0, 0, 0],
		[2, 0, 6, 7, 0, 0, 8, 4, 0],
		[5, 0, 3, 1, 0, 6, 9, 0, 2],
		[0, 7, 9, 0, 0, 4, 1, 0, 3],
		[0, 0, 0, 0, 5, 7, 0, 9, 0],
		[0, 9, 2, 0, 6, 8, 5, 0, 0],
		[0, 5, 0, 0, 0, 0, 0, 0, 6]
	]

def display_grid(g, x=-1, y=-1):
	"""
	Affiche la grille g en mettant en évidence la case (x, y).
	Les cases vides sont représentées par une étoile.
	"""
	j = 0
	for r in g:
		i = 0
		for e in r:
			if x!=-1 and y!=-1:
				f = '!' if (i==x and j==y) else ' '
			else:
				f = ''
			s = str(e) if e!=0 else '*'
			print f+s,
			i += 1
		print ''
		j += 1

#début des spoilers... ne pas regarder plus loin pour ne pas être influencé.
###############################################################################

def check_grid(g):
	"""
	Vérifie la grille passée en paramètre. Aucune optimisation...
	Retourne -1 si incorrecte, 0 si incomplète, 1 si correcte.
	"""
	for x in range(len(g[0])):
		for y in range(len(g)):
			if g[y][x] == 0:
				return 0 #valeur nulle donc pas complète
			elif not g[y][x] in get_candidates(g, x, y):
				return -1 #ça doit être la seule possibilité !
	return 1 #aucune case incorrecte

def get_candidates(g, x, y):
	"""
	Retourne les valeurs possibles pour une case (x, y) dans la grille g.
	La valeur déjà présente en (x, y) est ignorée (utile lors de la vérification).
	Algo : crible, c'est-à-dire qu'on élimine les valeurs non autorisées...
	TODO optimisation possible : passer par un bitmap pour les indiquer en retour.
	"""
	#candidats potentiels : tous
	cl = range(1, 10)
	#toute la colonne
	for py in range(0, len(g)):
		v = g[py][x]
		if (v in cl) and py!=y:
			cl.remove(v)
	#toute la ligne
	for px in range(0, len(g[0])):
		v = g[y][px]
		if (v in cl) and px!=x:
			cl.remove(v)
	#voisins dans la sous-grille
	gx = x / 3 * 3 #on calcule la position
	gy = y / 3 * 3 #... de la sous-grille
	for ox in range(0, 3):
		for oy in range(0, 3):
			px = gx+ox #on calcule une position absolue
			py = gy+oy #... par rapport à la sous-grille
			v = g[py][px]
			if (v in cl) and px!=x and py!=y:
				cl.remove(v)
	#ce qui reste est OK...
	return cl

def next_empty(g, x, y):
	"""
	Retourne la position de la prochaine case vide.
	Balayage colonne/ligne de GvD et HvB.
	"""
	while g[y][x] != 0:
		x += 1
		if x == len(g[0]):
			x = 0 #retour au début
			y += 1 #ligne suivante
			if y == len(g):
				#on est après la dernière...
				#plus rien à trouver
				return None
	return (x, y) #trouvée !

def solve(g, x, y):
	"""
	Résout la grille g en travaillant sur la case (x, y).
	Algorithme utilisé : backtracking.
	Retourne True si OK, False si impossible.
	"""
	assert(g[y][x] == 0) #on ne doit surtout pas modifier une donnée !
	cl = get_candidates(g, x, y)
	for c in cl:
		g[y][x] = c #on le place et on voit ce qu'il se passe...
		nx = next_empty(g, x, y) #prochaine case non vide
		if nx==None:
			return True #il n'y en a plus : on a fini !
		elif solve(g, nx[0], nx[1]):
			return True #toutes les suivantes (récursivement...) sont OK !
	g[y][x] = 0 #on la remet à zéro avant de revenir en arrière
	return False #impossible : on a tout essayé...


#Entrée
g = get_grid()
print u"Grille à résoudre"
display_grid(g)

#Calculs
print u"En cours...",
c = ticks()
f = next_empty(g, 0, 0)
r = solve(g, f[0], f[1])
print u"grille", (u"résolue" if r else u"impossible")
print u"Temps nécessaire :", ticks()-c, "msec"

#Sortie
display_grid(g)
print u"Vérification :", ("ok" if check_grid(g)==1 else "NOOOOOOOOOOOOOON !")